\section{Experimental Results}
\label{sec:results}

We report results on two variants of RW-BFS, namely, the sequential version RW-BFS$_s$ and the parallel version RW-BFS$_{p}$. The baseline in our comparison is LAMA~\cite{RichterHW08}, a best-first search planner. In our experiment, all three planners use the same settings and same heuristic functions for the best-first search part. We set $t = 4$ and let $l = 2 *j -1, n = 200 + 250j $ for $j = 1 \cdots t $ for both RW-BFS$_s$ and RW-BFS$_{p}$. In RW-BFS$_p$, line 3-8 in Algorithm 2 are running in parallel using $t = 4$ separate threads. The $open$ list is shared by these threads so that possible exit states discovered by these threads can be inserted into $open$ directly. We also set $m = 3000$,  $\delta = 0.2 h^{*} $, and $w = 10$. 

We test all domains in IPC-6~\cite{IPC6}, including Elevators~(Elevator), Openstacks~(Open), PARC printer~(Parc), Peg solitaire~(Peg), Scanalyzer-3D~(Scan), Sokoban, Transport~(Trans) and Woodworking~(Wood). All experiments are conducted on a quad core workstation with a $2.4$GHz CPU and 2GB memory. The running time limit for each instance is set to $300$ seconds. Figure~\ref{fig:statistic} shows the number of problem instances solved by the three planners. Clearly, both RW-BFS$_{s}$ and RW-BFS$_{p}$ solve more problem instances than the baseline planner. We have also run Monte-Carlo random walk (pure stochastic search) on these problems but its performance is poor and not reported here. 

\begin{figure}[htp]
  \centering
    \subfigure{\includegraphics[scale=0.44]{./figure/statistic.eps}}
\caption{\label{fig:statistic} \small Number of instances (out of all the instances in the testing domains) that are solvable for a given time limit.}
\vspace*{-0.05in}
\end{figure}

\input{./table/tb-plateau}

Figure~\ref{fig:statistic} shows that both RW-BFS$_{s}$ and RW-BFS$_{p}$ solve more problem instances than the baseline planner. They solve 233, 210, and 204 instances, respectively. We also give detailed comparisons of three planners on all IPC-6 problems for which {\it random walk exploration} is invoked. Problems without involving  {\it random walk exploration} are omitted from our comparison because in this case three algorithms are essentially identical. 

To show the contribution and overhead brought by random walk in RW-BFS$_{s}$, 
we also report the time spent in random walk (T'),
the length of the sub-path found by random exploration in
the final solution path (L'), and the number of heuristic evaluations
in random exploration procedure. For RW-BFS$_{p}$,
we report the length of the sub-path (L') in the final solution
path. We omit the time spent in random walk and the
number of heuristic evaluations in random exploration procedure
because these two metrics are in parallel to the runtime
overhead of best-first search in RW-BFS$_{p}$.

% Algorithm 2 is never called in RW-BFS, as all three algorithms are essentially identical in this case. 
% For both RW-BFS$_{s}$ and RW-BFS$_{p}$, we report their total solving time and the length of the subpath found by random exploration in the final solution path. For RW-BFS$_{s}$,  we also report time and number of heuristic function evaluations of random walks. 

% , along with the number of heuristic evaluations in random exploration procedure. For RW-BFS$_{p}$, we report the length of the sub-path (L) in the final solution path. 
%We omit the time spent in random walk and the number of heuristic evaluations in random exploration procedure because these two metrics are not relevant to the runtime overhead when random walks are running parallel to best-first search in RW-BFS$_{p}$.

We summarize three findings from Table~\ref{tb:plateau}. First, these results show that 
for problems where LAMA cannot solve within 300s, e.g., elevator-18, elevator-25, elevator-26, 
RW-BFS can successfully find a solution in which a substantial portion of the path is generated by random walks. These results clearly show that  random walks can assist best-first search
to escape from plateaus.  Second, comparing the performance of two sequential planners LAMA and RW-BFS$_{s}$ to RW-BFS$_{p}$, we see that the overhead brought in by alternating between random walk and best-first search can be mitigated by using a parallel implementation, at the cost of using more computing cores. Third, according to our performance analysis, if the state space has $q > 1$, the random walk procedure may not be helpful. A closer look at problems in the Pegsol domain reveals that they indeed have $q > 1$, as in this game, there can be multiple moves at each state and there can be multiple action paths arriving at the same state. Results on peg-29 and peg-30 confirmed our analysis that a random walk exploration would not assist the best-first search much when $q$ is close to $p$. In contrast, problems in the Sokoban domain are well-known to have many loops and dead ends. In this case, except for Sokoban-14, all subpaths generated by the random exploration procedures are all relatively short compared to the solution length, as a longer path would encounter more dead ends or loops. 

% Pegsol: http://en.wikipedia.org/wiki/Peg_solitaire

\nop{
In our experiments, all three algorithms find a solution easily in Openstacks, Peg solitaire, Scanalyzer-3D and Transport domains since problems in these domains rarely contain plateau.
Elevators, Sokoban and Woodworking domains usually have plateaus, which most are benches having an exit state. 
Thus, the LAMA search is frequently trapped into plateaus, which results in costing more search time or even failing to find a solution.
The results show that when LAMA is trapped into plateaus, calling MRW to try to finding an exit state can efficiently help LAMA to escape from plateaus.
The only special domain is PARC printer. 
It contains a large number of plateaus which are minimas having no exit.
The only way to jump out is expanding all states in these minimas.
}



%We would like to point out that problems that LAMA cannot solve within 300s are problems where there is a large plateau for it to explore. Both RW-BFS$_{s}$ and RW-BFS$_{p}$ solves more problems due to the fact that some plateau exploration are avoided during the search. 

%%%%% can be ignored 
\nop{

\input{./table/tb-statistic}

We also give a holistic view on the number of problem instances are solved in each domain by three planners 
in Figure~\ref{fig:statistic}. Clearly, both RW-BFS$_{s}$ and RW-BFS$_{p}$ solves more problem instances than our base planner. We would like to point out that problems that LAMA cannot solve within 300s are 
problems where there is a large plateau for it to explore. Both RW-BFS$_{s}$ and RW-BFS$_{p}$ solves more problems due to the fact that some plateau exploration are avoided during the search. 
%Table~\ref{tb:statistic} presents the number of instances solved in each individual domain. 
}


\nop{
We see from Table~\ref{tb:statistic} that both RW-BFS$_{s}$ and RW-BFS$_{p}$ solve more instances in PARC printer and Woodworking domains. Due to the non-deterministic nature of  both algorithms, 
 are overheads of switching from best-first search to random walk, 
in some problems instances like parc-24 and peg-29, the overall solving time 
for MW-BFS$_{s}$ is higher than that of LAMA. However, we can clearly see 
that parallel scheme mitigates this overhead on these problems. 
}